قالب وبلاگ

یافتن افزونگی در فایل
اکثرفایل های کامپیوتری ( با محتویات متفاوت ) دارای افزونگی اطلاعات می باشند. این نوع فایل ها دارای اطلاعات تکراری زیادی می باشند. برنامه های فشرده سازی اطلاعات ، اطلاعات تکراری  موجود در فایل ها را بر اساس الگوریتم های مربوطه حذف می نمایند. پس از تشخیص اطلاعات تکراری ، صرفا" اطلاعات تکراری یک بار در فایل تکرار و و در سایر موارد، از مکانیزمهای خاصی برای عدم تکرار استفاده می گردد.

جمله زیر از 17 کلمه ، 61 حرف ، 16 فضای خالی ، یک نقطه و یک dash ، تشکیل شده است :

اگر هر یک از حروف ، فضای خالی و حروف خاص ، یک واحد از حافظه را اشغال نمایند ، مجموعا" 79 واحد از حافظه توسط عبارت فوق استفاده خواهد گردید (79 = 1 + 1+ 16 + 61 ) . به منظور کاهش ظرفیت فایل می بایست  افزونگی اطلاعات در فایل را بررسی کرد. با مشاهده و بررسی عبارت فوق ، نتایج زیر بدست می آید :

·       کلمه "ask" ، دو مرتبه تکرار شده است .

·       کلمه "what" ،  دو مرتبه تکرار شده است .

·       کلمه "your" ، دو مرتبه تکرار شده است .

·       کلمه "country" ، دو مرتبه تکرار شده است .

·       کلمه "can" ، دو مرتبه تکرار شده است .

·       کلمه "do" ، دو مرتبه تکرار شده است .

·       کلمه "for" ، دو مرتبه تکرار شده است .

·       کلمه "you" ، دو مرتبه تکرار شده است .

با عدم لحاظ نمودن حروف بزرگ و کوچک درعبارت فوق ، مشاهده می گردد که نیمی از اطلاعات موجود در عبارت فوق ، زائد و تکراری می باشند. با دقت در عبارت فوق و نحوه افزونگی اطلاعات مشاهده می گردد که با دارا بودن نه کلمه ask,not,what,your,country,can ،do ،for  و you می توان پالایشی مناسبی از عبارت فوق را انجام و در صورت لزوم و با استفاده از نه کلمه فوق ، مجددا" عبارت اولیه را ایجاد نمود. در این راستا و به منظور ایجاد عبارت فوق کافی است به کلمات موجود در بخش اول ( نصف عبارت ) اشاره  و جایگاه و تعداد تکرار هر یک از آنها را در بخش دوم مشخص نمود. در ادامه نحوه فشرده سازی اطلاعات و بازسازی مجدد آنها بررسی می گردد.

فشرده سازی اطلاعات
اکثر برنامه های فشرده سازی از مدل ها ی متفاوت الگوریتم مبتنی بر دیکشنری  ایجاد شده توسط "Lempel و Ziv"  ، به منظور کاهش ظرفیت فایل ها ، استفاده می نمایند. منظور از دیکشنری در الگوریتم فوق ، روش های کاتولوگ نمودن بخش هائی از داده است . سیستم استفاده شده برای سازماندهی  دیکشنری متفاوت و در ساده ترین حالت می تواند شامل یک لیست عددی باشد.  با مراجعه مجدد به عبارت اشاره شده در بخش قبل ، کلمات تکراری را انتخاب و آنها را در لیست مرتب شده ای بصورت زیر ایندکس می نمائیم . پس از ایجاد لیست فوق ، می توان در مواردیکه از کلمات در عبارت استفاده می شود ، از اعداد نسبت داده شده و متناظر با آنها استفاده کرد. دیکشنری ایجاد شده برای عبارت اشاره شده در بخش قبل بصورت زیر است :

با توجه به دیکشنری ایجاد شده ، عبارت مورد نظر بصورت زیر خوانده خواهد شد :

برای بازسازی مجدد عبارت فوق ، لازم است الگوی معادل آن را با توجه به دیکشنری استخراج و در محل مربوطه قرار داد. برنامه هائی نظیر WinZip از فرآیندهای مشابه برای بازسازی مجدد یک فایل و برگرداندن آن به شکل اولیه استفاده می نمایند.
در فرآیند فشرده سازی عبارت اشاره شده در بخش قبل به شکل جدید آن ( مطابق جدول بالا ) چه میزان ظرفیت فایل کاهش پیدا کرده است ؟ مطمئنا" عبارت فشرده شده ظرفیت کمتری نسبت به عبارت اولیه خواهد داشت . در این زمینه لازم است به این نکته مهم اشاره گردد که دیکشنری ایجاد شده نیز می بایست بهمراه فایل ذخیره گردد. در مثال فوق ، عبارت اولیه برای ذخیره سازی به 79 واحد حافظه نیاز داشت . عبارت فشرده شده ( بهمراه فضای خالی ) ، 37 واحد و دیکشنری ( کلمات و اعداد )  ، نیز 37 واحد حافظه را اشغال خواهند کرد. بدین ترتیب ظرفیت فایل فشرده به 74 واحد حافظه خواهد رسید . با توجه به اطلاعات فوق مشاهده می گردد که عملا" در رابطه با فشرده سازی عبارت فوق به موفقیت های بزرگی نائل نشده ایم . در این زمینه لازم است به این نکته اشاره  گردد که در مثال فوق ،  صرفا" یک " جمله "  فشرده شده است .  فرض کنید جمله فوق بخشی از یک سخنرانی یک ساعته باشد ، بدیهی است که در سخنرانی فوق احتمال تکرار کلمات فوق بسیار زیاد خواهد بود . با ایجاد سیستم دیکشنری  ، زمینه استفاده از آن در بخش های بعدی سخنرانی نیز وجود داشته و در ادامه قطعا" میزان فشرده سازی  جملات موجود در متن سخنرانی نتایج مطلوبتری را بدنبال خواهد داشت .

جستجو برای الگوها
در مثال ارائه شده ، تمام کلمات تکراری انتخاب و در دیکشنری قرار گرفتند. در روش فوق ، ساده ترین مدل برای ایجاد دیکشنری استفاده شده است . برنامه های فشرده سازی از مدل های کاملا" متفاوت دیگر در این زمینه استفاده می نمایند.برنامه های فوق نسبت به کلمات متمایز، از یکدیگر شناخت لازم را نداشته و در این راستا صرفا" بدنبال "الگو" خواهند بود. این نوع برنامه ها به منظور کاهش ظرفیت فایل ها ، با دقت الگوها را انتخاب و آنها را در دیکشنری مستقر می نمایند.   در صورتی که از دیدگاه فوق فرآیند فشرده سازی دنبال گردد ، در نهایت  با یک دیکشنری کاملا" متفاوت با آن چیزی که قبلا" ایجاد شده بود ، مواجه خواهیم بود.
اگر یک برنامه فشرده سازی عبارت معروف اشاره  شده در بخش قبل را به منظور یافتن افزونگی ، پیمایش نماید ، پس از دنبال نمودن بخشی از عبارت (ask not what your) ، الگوئی جدید را تشخیص خواهد داد. الگوی فوق حرف "t" بوده که بدنبال آن یک فضای خالی نیز قرار دارد. ( در کلمات "not" و "what" ) . در صورتی که برنامه فشرده سازی الگوی فوق را در دیکشنری مستقر نماید ، می بایست یک عدد "1" را در هر زمان که با  حرف "t"  و یک فضای خالی بدنبال آن برخورد می نماید ، در دیکشنری ثبت نماید. با ادامه پیمایش عبارت فوق توسط برنامه فشرده سازی ، مشاهده می گردد که الگوی تشخیص داده شده ( حرف t و فضای خالی بدنبال آن ) به میزان قابل ملاحظه ای در عبارت تکرار نشده و برای ثبت در دیکشنری واجد شرایط مناسب نخواهد بود ، بدین تزتیب الگوی تشخیص داده شده نادیده گرفته شده و عملیات یافتن الگوئی دیگر ، دنبال خواهد گردید.
در ادامه برنامه فشرده سازی  متوجه الگوی "ou" می گردد ، الگوی فوق در کلمات "your" و "country" ، تکرار شده است . در صورتی که عبارت مورد نظر یک فایل طولانی بود ، ثبت و نوشتن الگوی فوق در دیکشنری می توانست به میزان قابل توجه ای از ظرفیت فایل را کاهش دهد. "ou" ، یکی از ترکیبات متداول استفاده شده  در زبان انگلیسی است . معیار برنامه فشرده  سازی عبارتی است که در حال پیمایش آن است . در ادامه پیمایش عبارت فوق ، یک الگوی مناسبتر تشخیص داده خواهد شد. الگوهای فوق "your"  و "country" بوده که هر یک بدفعات  تکرار شده اند. تکرار هر یک از کلمات فوق در عبارت معادل ترکیب کلمات "your country" است . در چنین حالتی برنامه قشرده سازی  entry موجود در دیکشنری برای الگوی "ou" را با الگوی "your country" ، جایگزین می نماید. عبارت ترکیبی "can do for" ، نیز در عبارت اصلی تکرار شده است . ( یک مرتبه پس از "your" و یک مرتبه پس از "you" ) . بدین ترتیب الگوی "can do for you" نیز تکراری خواهد بود. بنابراین می توان در عوض نوشتن 15 حرف ( بهمراه قضای خالی ) ، از یک عدد استفاده کرد. در صورت استفاده از الگوی "your country" ، برای 13 حرف از یک عدد معادل استفاده می گردد ، بدیهی است که الگوی فوق نادیده گرفته شده  در عوض  الگوی "r country"  و الگوی جدید  "can do fo you" ، در دیکشنری ثبت می گردند. برنامه فشرده سازی فرآیند فوق را دنبال و پس از یافتن یک الگو ، محاسبات مربوطه  را انجام و الگوی واجدالشرایط را در دیکشنری ثبت خواهد کرد. مهمترین ویژگی "الگوریتم مبتنی بر دیکشنری " ، قابلیت تغییر الگوها در زمان فرآیند فشرده سازی است .
با توجه به الگوهائی تشخیص داده شده ، دیکشنری مربوطه بشکل زیر خواهد بود . در دیکشنری زیر الگوهای تشخیص داده شده ثبت و برای فضای خالی از کاراکتر "__" استفاده شده است .

با توجه به دیکشنری فوق ، عبارت اشاره شده در بخش قبل بصورت زیر فشرده می گردد.

 عبارت فوق 18 و  دیکشنری 41 ،  واحد حافظه را اشغال خواهند کرد. بدین ترتیب فایل حاوی عبارت اولیه فوق از 79 واحد حافظه به 59 واحد حافظه کاهش پیدا کرده است . روش استفاده شده به منظور فشرده سازی عبارت فوق یکی از امکانات موجود بوده و می توان در این راستا از روش های دیگر نیز استفاده کرد.

تا چه میزان می توان  اطلاعات را فشرده کرد ؟
میزان ( نسبت ) کاهش ظرفیت یک فایل ،  به عوامل متعددی نظیر : نوع فایل ،  اندازه فایل و روش فشرده سازی بستگی دارد. در اکثر زبانهای طبیعی ،  حروف و کلمات الگوهای مناسبی را بصورت جداگانه و یا ترکیبی ایجاد می نمایند. بدین ترتیب فشرده سازی فایل های متنی  نتایج بسیار مطلوبی را بدنبال خواهد داشت . فایل های متنی اغلب پس از فشرده سازی به میزان پنجاه درصد و یا بیشتر ،  کاهش ظرفیت را خواهند داشت . اکثر زبانهای برنامه نویسی ( مصنوعی ) نیز بدلیل استفاده از مجموعه ای از دستورات که بصورت تکراری استفاده می شوند ، دارای افزونگی  اطلاعات بوده و پس از فشرده سازی نتایج رضایتبخشی  را بدنبال خواهد داشت . فایل هائی که دارای حجم بالائی از اطلاعات منحصر بفرد بوده ( نظیر فایل های گرافیک و یا فایل های mp3) ،  بدلیل عدم وجود الگوهای تکرار شونده ،  بخوبی فشرده نخواهند گردید.
در صورتی که فایلی دارای تعداد زیادی الگوی تکرار شونده باشد ،  میزان افزونگی اطلاعات موجود در فایل بطرز محسوسی ظرفیت فایل را افزایش خواهد داد. بدین ترتیب در زمان فشرده سازی این نوع از فایل ها با توجه به وجود الگوهای تکرار شونده ،  ظرفیت فایل در حد قابل قبولی کاهش پیدا خواهد کرد .
میزان فشرده سازی اطلاعات،   به الگوریتم استفاده شده  توسط برنامه فشرده سازی نیز بستگی دارد. بدیهی است استفاده از یک الگوریتم با کارآئی بالا ،  نتایج مثبتی را در رابطه با فشرده سازی به ارمغان خواهد آورد.